﻿namespace Leetcode.N6066;
public class CountIntervals
{

    private readonly IList<int[]> list = new List<int[]>();
    private int count = 0;

    public void Add(int left, int right)
    {
        var findLeft = this.FindLeft(left);
        var findRight = this.FindRight(findLeft.index, right);

        for (int i = findRight.index; i >= findLeft.index; i--)
        {
            this.count -= this.list[i][1] - this.list[i][0] + 1;
            this.list.RemoveAt(i);
        }

        this.list.Insert(findLeft.index, new int[] { findLeft.left, findRight.right });
        this.count += findRight.right - findLeft.left + 1;
    }

    public int Count()
    {
        return this.count;

    }

    private (int index, int left) FindLeft(int left)
    {
        var from = 0;
        var to = this.list.Count - 1;
        while (from <= to)
        {
            var m = from + (to - from) / 2;
            var item = this.list[m];

            if (left < item[0])
            {
                to = m - 1;
            }
            else if (left > item[1])
            {
                from = m + 1;
            }
            else
            {
                return (m, Math.Min(this.list[m][0], left));
            }
        }
        return (from, left);
    }

    private (int index, int right) FindRight(int fromIndex, int right)
    {
        var from = fromIndex;
        var to = this.list.Count - 1;
        while (from <= to)
        {
            var m = from + (to - from) / 2;
            var item = this.list[m];

            if (right < item[0])
            {
                to = m - 1;
            }
            else if (right > item[1])
            {
                from = m + 1;
            }
            else
            {
                return (m, Math.Max(item[1], right));
            }
        }
        return (from - 1, right);
    }
}